package leetcode.剑指offer.前40;

import org.junit.Test;

/**
 * @author ：zsy
 * @date ：Created 2021/7/17 23:10
 * @description：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
 */
public class 剑指_04_二维数组中的查找 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.findNumberIn2DArray(
                new int[][]{
                        {1,   4,  7, 11, 15},
                        {2,   5,  8, 12, 19},
                        {3,   6,  9, 16, 22},
                        {10, 13, 14, 17, 24},
                        {18, 21, 23, 26, 30}
                        },
                        5));
    }

    class Solution {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            /*
            // 简单解法
            int rowLen = matrix.length;
            if (rowLen == 0) return false;
            int colLen = matrix[0].length;
            int i = 0;
            for (int j = colLen - 1; j >= 0; j--) {
                while (matrix[i][j] < target) {
                        i++;
                if (i == rowLen) return false;
                }
                if (matrix[i][j] == target) return true;
            }
            return false;
             */
            if(matrix.length == 0 || matrix[0].length == 0) return false;
            int row = matrix.length;
            int col = matrix[0].length;
            int[] cols = new int[row];
            for (int i = 0; i < row; i++) {
                cols[i] = matrix[i][0];
            }
            int rowIndex = binarySearch(cols, target);
            if (rowIndex == -1) return false;
            for (int i = 0; i < rowIndex; i++) {
                int fIndex = binarySearch(matrix[i], target);
                    if (fIndex != -1 && matrix[i][fIndex] == target) {
                    return true;
                }
            }
            return false;
        }

        public int binarySearch(int[] nums, int tar) {
            int l = 0;
            int r = nums.length - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= tar) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            return nums[l] <= tar ? l : -1;
        }
    }

}
